// https://leetcode.cn/problems/binary-tree-maximum-path-sum/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 后序遍历递归求解二叉树中的最大路径和
// 2. 路径定义：任意节点到任意节点的序列，节点最多出现一次
// 3. 递归返回以当前节点为端点的最大路径和（单边）
// 4. 更新全局最大值：左路径+当前节点+右路径
// 5. 时间复杂度：O(n)，空间复杂度：O(h)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    int ret;

    int maxPathSum(TreeNode* root) 
    {
        ret = -0x3f3f3f3f;
        recur(root);

        return ret;
    }

    int recur(TreeNode* root)
    {
        if (root == nullptr) 
        {
            return 0;
        }

        int left = 0, right = 0;

        left = max(0, recur(root->left));
        right = max(0, recur(root->right));

        ret = max(ret, left + right + root->val);

        return max(left, right) + root->val;
    }
};

int main()
{
    vector<string> nodes1 = {"1","2","3"};
    vector<string> nodes2 = {"-10","9","20","null","null","15","7"};

    Solution sol;

    auto root1 = buildTree(nodes1);
    auto root2 = buildTree(nodes2);

    cout << sol.maxPathSum(root1) << endl;
    cout << sol.maxPathSum(root2) << endl;

    return 0;
}